package Algorithm.Sort;

public class QuickSort {
    public static void main(String[] args) {
        int[] nums = {5,6,1,4,9,3,10,11,13};
//        int[] nums = {1,4,3};
//
//        quickSort(nums,0, nums.length-1);
//        for (int i:nums){
//            System.out.print(""+i+" ");
//        }

//        heapSort(nums);
    }

    public static void quickSort(int nums[], int l, int r){
        if (l>=r)
            return;
        int temp = nums[l];
        int ll = l;
        int rr = r;
        while (ll<rr){
            while (nums[rr] >= temp && ll<rr){
                rr--;
            }
            nums[ll] = nums[rr];

            while (nums[ll]<=temp && ll<rr){
                ll++;
            }
            nums[rr] = nums[ll];
        }

        nums[ll] = temp;
        quickSort(nums,l,ll-1);
        quickSort(nums,rr+1,r);
    }

    public static void heapSort(int nums[]){
        for (int i= nums.length/2-1;i>=0;i--){
            adjustHeap(nums,i,nums.length);
        }

        for (int j=nums.length-1;j> 0;j--){
            swap(nums,0,j);
            adjustHeap(nums,0,j);
        }
        System.out.println("");
        for (int i:nums){
            System.out.print(""+i+" ");
        }
    }

    public static void adjustHeap(int[] nums, int i,int j){
        int temp = nums[i];

        while ((2*i+1)<j){
            int index = 2 * i + 1;
            int maxIndex = index;
            if ((index+1)<j&&nums[index]<nums[index+1])
                maxIndex = index + 1;
            if (temp<nums[maxIndex]){
                nums[i] = nums[maxIndex];
            }else {
                break;
            }
            i = maxIndex;
        }
        nums[i] = temp;
    }

    public static void swap(int[] nums, int i, int j){
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }

}
